package com.cuz.daileetcode.bat100;

public class 无限张指定容量装满背包最大价值 {
    public static void main(String[] args) {
        int[] volume = {2, 2, 3, 4, 5, 1};
        int[] value = {4, 3, 10, 7, 1, 3};
        System.out.println(solution1(volume, value, 10));
        System.out.println(solution2(volume, value, 10));
    }
    public static int solution1(int[] volume, int[] value, int v) {
        int things = value.length;
        int[][] dp = new int[things][v + 1];
        //这个背包允许我们装以下第一个物品
        //v / volume[0] 表示当前背包最多装多少个体积为volume[0]的物品
        for (int i = 0; i <= v / volume[0]; i++) {
            //选择i个0位置物品 装好的体积就是volume[0] * i
            //价值就是i * value[0]
            dp[0][volume[0] * i] = i * value[0];
        }
        for (int row = 1; row < things; row++) {
            for (int col = 0; col <= v; col++) {
                //不选择当前物品 也就是说0~row-1 物品随便选择的最大价值
                dp[row][col] = dp[row - 1][col];
                //选择i个当前位置的物品
                int chooseCur = 0;
                for (int i = 1; i <= (col / volume[row]); i++) {
                    //选择i个体积不能大于当前体积col
                    //选择i个当前物品的价值  + 0~row位置物品随便选凑出col - i * volume[row]体积的价值
                    chooseCur = Math.max(i * value[row] + dp[row-1][col - i * volume[row]]
                            , chooseCur);
                }
                //取大者
                dp[row][col] = Math.max(chooseCur, dp[row][col]);
            }
        }
        return dp[things - 1][v] == 0 ? -1 : dp[things - 1][v];
    }

    public static int solution2(int[] volume, int[] value, int v) {
        int things = value.length;
        int[][] dp = new int[things][v + 1];
        //这个背包允许我们装以下第一个物品
        //v / volume[0] 表示当前背包最多装多少个体积为volume[0]的物品
        for (int i = 0; i <= v / volume[0]; i++) {
            //选择i个0位置物品 装好的体积就是volume[0] * i
            //价值就是i * value[0]
            dp[0][volume[0] * i] = i * value[0];
        }
        for (int row = 1; row < things; row++) {
            for (int col = 0; col <= v; col++) {
                //不选择当前物品 也就是说0~row-1 物品随便选择的最大价值
                dp[row][col] = dp[row - 1][col];
                //选择i个当前位置的物品
                if (col - volume[row] >= 0) {
                    int chooseCur = value[row] + dp[row][col - volume[row]];
                    dp[row][col] = Math.max(chooseCur, dp[row][col]);
                }
            }
        }
        return dp[things - 1][v] == 0 ? -1 : dp[things - 1][v];
    }

}
